package leetcode;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-5-30
 * Time: 下午8:01
 * To change this template use File | Settings | File Templates.
 */

public class Solution4_2 {
    public ListNode sort(ListNode head){
        if(head==null || head.next==null){
            return head;
        }
        else{
            int i=0;
            ListNode head1 = head;
            while(head1!=null){
                i++;
                head1 = head1.next;
            }
            int j=0;
            ListNode head2 = head;
            while(j<i/2-1){
                head2 = head2.next;
                j++;
            }
            head1 = head2.next;
            head2.next = null;

            ListNode head11 = sort(head1);
            ListNode head22 = sort(head);
            ListNode headFinal = merge(head11,head22);
            return headFinal;
        }
    }
    public ListNode merge(ListNode head1,ListNode head2){
        ListNode headTmp1,headTmp2,headlast1,headlast2,head;
        headlast1 = null;
        headlast2 = null;
        head = head2;
        headTmp2 = head2;
        headTmp1 = head1;
        if(headTmp2==null){
            return headTmp1;
        }
        while(headTmp1!=null){
            if(headTmp1.val>headTmp2.val){
                for(;headTmp2!=null && headTmp1.val>headTmp2.val;headlast2=headTmp2,headTmp2=headTmp2.next);
                if(headTmp2==null){
                    headlast2.next = headTmp1;
                    for(;headTmp1!=null;headTmp1 = headTmp1.next);
                }
                else{
                    headlast2.next = headTmp1;
                    headlast1 = headTmp1;
                    headTmp1 = headTmp1.next;
                    headlast1.next = headTmp2;
                    headTmp2 = head;
                }
            }
            else{
                head = headTmp1;
                headTmp1 = headTmp1.next;
                head.next = headTmp2;
                headTmp2 = head;
            }
        }

        return head;
    }
    public ListNode sortList(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode judgeNode = head.next;
        ListNode lastNode = head;
        ListNode leftHead = head;
        int leftCount = 1;
        int rightCount = 1;                      //head属于left也属于right
        while(judgeNode!=null){
            if(judgeNode.val<head.val){
                ListNode tmp = judgeNode;
                lastNode.next = judgeNode.next;
                lastNode = lastNode.next;
                judgeNode.next = head;
                leftHead = judgeNode;
                judgeNode = tmp.next;
                leftCount++;
            }
            else{
                lastNode = lastNode.next;
                judgeNode = judgeNode.next;
                rightCount++;
            }
        }
        ListNode head11 = sortLeft(leftHead, leftCount);
        sortRight(head,rightCount);
        ListNode headFinal = head11;
        return headFinal;
    }

    private ListNode sortLeft(ListNode head, int length) {
        if(length<=2){
            return head;
        }
        ListNode judgeNode = head.next.next;
        ListNode lastNode = head;
        ListNode leftHead = head;
        int leftCount = 1;
        int rightCount = 1;                      //head属于left也属于right
        while(judgeNode!=null){
            if(judgeNode.val<head.val){
                ListNode tmp = judgeNode;
                lastNode.next = judgeNode.next;
                judgeNode.next = head;
                leftHead = judgeNode;
                judgeNode = tmp.next;
                leftCount++;
            }
            else{
                lastNode = lastNode.next;
                judgeNode = judgeNode.next;
                rightCount++;
            }
        }
        ListNode head11 = sortLeft(leftHead, leftCount);
        sortRight(head,rightCount);
        ListNode headFinal = head11;
        return headFinal;

    }

    private void sortRight(ListNode head, int length) {
        if(length>2){
            ListNode judgeNode = head.next.next;
            ListNode lastNode = head.next;
            ListNode leftHead = head.next;
            int leftCount = 1;
            int rightCount = 1;                      //head属于left也属于right
            while(judgeNode!=null){
                if(judgeNode.val<head.val){
                    ListNode tmp = judgeNode;
                    lastNode.next = judgeNode.next;
                    judgeNode.next = head;
                    leftHead = judgeNode;
                    judgeNode = tmp.next;
                    leftCount++;
                }
                else{
                    lastNode = lastNode.next;
                    judgeNode = judgeNode.next;
                    rightCount++;
                }
            }
            ListNode head11 = sortLeft(leftHead, leftCount);
            sortRight(head,rightCount);
            ListNode headFinal = head11;
        }
    }

    public static void main(String[] args){
        ListNode A = new ListNode(4);
       /* A.next = new ListNode(19);
         A.next.next = new ListNode(14);
        A.next.next.next = new ListNode(5);
        A.next.next.next.next= new ListNode(-3);
        A.next.next.next.next.next= new ListNode(1);
        A.next.next.next.next.next.next= new ListNode(8);
        A.next.next.next.next.next.next.next= new ListNode(5);
        A.next.next.next.next.next.next.next.next= new ListNode(11);
        A.next.next.next.next.next.next.next.next.next= new ListNode(15);*/
        Solution4 solution4 = new Solution4();
        ListNode B = solution4.sortList(A);
        System.out.println(B.val);
      /* System.out.println(B.next.val);
        System.out.println(B.next.next.val );
        System.out.println(B.next.next.next.val );
        System.out.println(B.next.next.next.next.val );
        System.out.println(B.next.next.next.next.next.val );
        System.out.println(B.next.next.next.next.next.next.val );
        System.out.println(B.next.next.next.next.next.next.next.val );
        System.out.println(B.next.next.next.next.next.next.next.next.val );
        System.out.println(B.next.next.next.next.next.next.next.next.next.val );*/
       /*System.out.println(B.next.next.next.val );*/
    }
}
